package com.atwy.linearstructure.stack;

import java.util.Scanner;

/**
 * @Author: 小王子火
 * @Date: 2020/11/29
 * <p>
 * 用栈实现一个简单的计算器
 * 1、数字栈
 * 2、符号栈
 * 思路：
 */
public class Calculator {

    public static void main(String[] args) {

        /*Scanner scanner = new Scanner(System.in);
        boolean loop = true;
        char key = ' ';
        while (loop) {
            System.out.println("c:进行计算");
            System.out.println("e:退出");
            key = scanner.next().charAt(0);
            switch (key) {
                case 'c':
                    System.out.println("请输入计算表达式，例如2+3*6-4");
                    String nextLine = scanner.next();
                    int result = calculate(nextLine);
                    // 输出结果
                    System.out.printf("%s=%d\n",nextLine,result);
                    break;
                case 'e':
                    scanner.close();
                    loop = false;
                    break;
                default:
                    break;
            }
        }
        System.out.println("程序已退出~");*/

        int calculate = calculate("8*1-2+2*3*1");
        System.out.println(calculate);
        calculate = calculate("20*30-10*20+11");
        System.out.println(calculate);
    }


    public static int calculate(String express) {

        //express = "7-3*2+1";
        // 定义一个11位数字栈
        ArrayStack2 numStack = new ArrayStack2(11);

        // 定义一个符号栈
        ArrayStack2 sigStack = new ArrayStack2(10);

        int index = 0;
        int num1 = 0;
        int num2 = 0;
        int oper = 0;
        int result = 0;
        String keepNum = "";
        // 此循环将数字入数栈，符号入符号栈，相邻运算符同级或者后小于前，将计算前表达式
        // 第二个循环，将取出数栈和符号栈中的数据，依顺序进行计算，此时符号栈中只有三种可能，
            // 1、没有符号；2、只有一个符号 ；3、有两个符号。无论哪种都可以按顺序弹出进行计算
        // 遍历表达式express的每个字符，入栈
        while (true) {
            char ch = express.substring(index, index + 1).charAt(0);
            // 当前字符为符号
            if (sigStack.isOper(ch)) {

                if (sigStack.isEmpty()) {
                    sigStack.push(ch);
                } else if(sigStack.priority(ch)<= sigStack.priority(sigStack.peek())){
                    // 先弹出第二个数，
                    num2 = numStack.pop();
                    num1 = numStack.pop();
                    oper = sigStack.pop();
                    result = numStack.cal(num1, num2, oper);
                    // 如7-2*3+1，当此时ch='+'时，7-6+1，需要再判断前面的符号
                    if( sigStack.isNotEmpty() && sigStack.priority(ch)<= sigStack.priority(sigStack.peek())){
                        num2 = result;// 第二个数就是上面的计算结果
                        num1 = numStack.pop();
                        oper = sigStack.pop();
                        result = numStack.cal(num1,num2,oper);
                    }
                    // 将计算结果入栈
                    numStack.push(result);
                    // 新符号入栈
                    sigStack.push(ch);
                }else{
                    // 如果当前操作符的优先级大于栈中的操作符，直接入栈
                    sigStack.push(ch);
                }

            } else {// 不是符号
                // char 和 int 转换，用于一位数的计算
                //numStack.push(ch - '0');

                // 如果多位数
                keepNum += ch;

                // 如果是最后一个字符
                if(express.length() -1 == index){
                    numStack.push(Integer.parseInt(keepNum));
                    break;
                }

                // 下一个符号此时keepNum就是完整的数
                char nextCh = express.substring(index+1,index+2).charAt(0);
                if(sigStack.isOper(nextCh)){
                    numStack.push(Integer.parseInt(keepNum));
                    keepNum = "";// 置空
                }
            }

            if (express.length() - 1 == index) {
                break;
            }
            index++;
        }
        // 第二次循环
        while (true){
            // 可以判断数栈是否为空，也可以判断符号栈是否为空，
            if(numStack.isEmpty()){
                break;
            }
            num2 = numStack.pop();
            num1 = numStack.pop();
            oper = sigStack.pop();
            result = numStack.cal(num1,num2,oper);
            // 如果此时数栈为空，说明计算结束
            if(numStack.isEmpty()){
                break;
            }
            // 否则将计算结果入数栈
            numStack.push(result);
        }
        return result;
    }
}

class ArrayStack2 {
    /**
     * 栈的大小
     */
    private int maxSize;
    /**
     * 数组模拟栈，数据存放的地方
     */
    private int[] stack;
    /**
     * top表示栈顶，初始化为-1
     */
    private int top = -1;

    /**
     * 构造器
     */
    public ArrayStack2(int maxSize) {
        this.maxSize = maxSize;
        stack = new int[this.maxSize];
    }

    /**
     * 判断栈是否已满，如果栈中元素个数为0，即maxSize=0，此时栈既是满的也是空的
     */
    public boolean isFull() {
        return top == maxSize - 1;
    }

    /**
     * 判断栈是否为空
     */
    public boolean isEmpty() {
        return top == -1;
    }

    /**
     * 不为空返回true
     * @return
     */
    public boolean isNotEmpty(){
        return !isEmpty();
    }

    /**
     * 入栈操作，入栈前要检验栈是否已满
     */
    public void push(int value) {
        if (isFull()) {
            System.out.println("栈已满，不能添加数据");
            return;
        }
        top++;
        stack[top] = value;
    }

    /**
     * 出栈，出栈前要判断栈是否为空
     */
    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("栈为空，无数据可取~");
        }
        int value = stack[top];
        top--;
        return value;
    }

    /**
     * 瞅一眼，不弹出
     * @return
     */
    public int peek(){
        if (isEmpty()) {
            throw new RuntimeException("栈为空，无数据~");
        }
        return stack[top];
    }

    /**
     * 打印栈的数据，从栈顶到栈底的顺序
     */
    public void show() {
        if (isEmpty()) {
            System.out.println("栈空，无数据可显示~");
            return;
        }
        for (int i = top; i >= 0; i--) {
            System.out.printf("stack[%d]=%d\n", i, stack[i]);
        }
    }

    /**
     * 判断 c 是不是字符
     *
     * @param c
     * @return true - 表示是字符
     */
    public boolean isOper(char c) {
        return c == '+' || c == '-' || c == '*' || c == '/';
    }

    /**
     * 运算符的优先级
     *
     * @param c
     * @return
     */
    public int priority(int c) {
        if (c == '*' || c == '/') {
            return 1;
        } else if (c == '+' || c == '-') {
            return 0;
        } else {
            System.out.println("运算符错误");
            return -1;
        }
    }

    /**
     * 计算得到结果
     *
     * @param num1
     * @param num2
     * @param oper
     * @return
     */
    public int cal(int num1, int num2, int oper) {
        int res = 0;
        switch (oper) {
            case '+':
                res = num1 + num2;
                break;
            case '-':
                res = num1 - num2;
                break;
            case '*':
                res = num1 * num2;
                break;
            case '/':
                res = num1 / num2;
            default:
                break;

        }
        return res;
    }
}
